The present invention relates generally to a method and system for computer aided design (CAD) of integrated circuits and in particular to finding a shortest way for routing a path.
Wires are typically layers of conductive metal material such as copper or aluminum that are separated by layers of insulating material such as silicon dioxide. The metal layers are patterned using photolithographic techniques to form the wires for interconnecting the electrical elements in an integrated circuit (IC). The design or layout of a complex IC may, in part, be automated such that the location of interconnection wires, hereinafter also referred to as “wires,” is determined with the aid of CAD software called a router. Nanometer physical design is facing increasing challenges from process limitations, such as lithography printability, topology variation, random defects, and the like. Since many process limitations are interconnection-related, the routing step is considered important to address these challenges.
In general, routing methods to handle process limitations are categorized into the model-based and rule-based approaches. The model-based approach is to design models to capture manufacturing effects, which is used to guide routers for layout optimization. Conversely, the rule-based approaches translate process limits into design rules to be followed by routers.
Many model-based approaches have been proposed including a predictive copper chemical-mechanical planarization model, used in a global router to minimize topology variations, a model using random defects as critical areas, and other related critical area minimization methods. Additionally, an effective redundant wire insertion algorithm has been proposed to tolerate potential wire opens. Lithography diffractions are also addressed in some models. Yet, to minimize the impact on routing runtime, the above proposed models are simplified and the modeling accuracy may be compromised.
In contrast to model-based approaches, only a few rule-based approaches have been published. In nanometer technology nodes, foundries impose numerous wiring design rules, hereinafter also referred to as “wiring rules” or “rules” on chip layout. Yet, these rules can incapacitate existing routing algorithms and lengthen the computer run time to route the IC, i.e. effect the ability of the computer to route paths.
Thus there is a need for a better router that provides short computer run times and short routing paths that are legal by design rules.